The present invention relates generally to database queries, and more specifically, to queries of encrypted databases.
In many systems including databases of encrypted information such as financial and medical databases, for example, substantial parts of the databases must be decrypted only by secure hardware because of regulatory or other reasons. These encrypted databases are considered host-opaque because even the host that stores the database may not access the database contents. Instead, only one or more secure processors (secure coprocessors) may access the database. In such systems, when the database size exceeds the total capacity of the secure coprocessors, a large latency can result in conducting a traditional search. This can be especially true when data mining encrypted databases because data mining generally involves searching for correlations between different properties of database records.